package 力扣_链表.双指针;

import java.util.HashSet;

/**
 * @author zx
 * @create 2022-08-15 15:30
 */
public class 面试题_链表相交 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            // 若相交,则会在公共处起点相遇。
            // 若不相交,相遇处是NULL
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pB;//pA或pB都行
    }

    /**
     * @return 哈希表
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)){
                return headB;
            }else{
                headB = headB.next;
            }
        }
        return null;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
        next = null;
    }
}